#include <cstdio>
#include <algorithm>
using namespace std;
int solve(int m,int n){
    if(n==1 || m==1 || m==0){
        return 1;
    }
    if(m<n){
        return solve(m,m);
    }
    else{
        return solve(m,n-1)+solve(m-n,n);
    }
}
int main(void){
    int t,m,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&n);
        int ans=solve(m,n);
        printf("%d\n",ans);
    }
    return 0;
}
